package own.stu.jobgib.playown.alg.string;

public class BM {

    private static final int SIZE = 256;

    /**
     * 散列表 数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置
     *
     * @param b 模式串
     * @param len 模式串长度
     * @param table 散列表
     */
    private static void generateHashTable(char[] b, int len, int[] table){

        // 初始化散列表
        for(int i = 0; i < SIZE; i ++){
            table[i] = -1;
        }

        for(int i = 0; i < len; i ++){
            table[(int)b[i]] = i;
        }

    }

    public static int bm(char[] a, int n, char[] b, int m) {
        int[] table = new int[SIZE];    // 记录模式串中每个字符最后出现的位置
        generateHashTable(b, m, table); // 构建坏字符哈希表
        int i = 0;                      // i 表示主串与模式串对齐的第一个字符
        while (i <= n - m) {
            int j;
            for (j = m - 1; j >= 0; j--) {   // 模式串从后往前匹配
                if (a[i + j] != b[j]) break; // 坏字符对应模式串中的下标是 j
            }
            if (j < 0) {
                return i;                   // 匹配成功，返回主串与模式串第一个匹配的字符的位置
            }
            // 这里等同于将模式串往后滑动 j-bc[(int)a[i+j]] 位
            i = i + (j - table[(int) a[i + j]]);
        }
        return -1;
    }

    public static void main(String[] args) {
        String pattern = "abxh";
        int[] table = new int[SIZE];
        generateHashTable(pattern.toCharArray(), pattern.length(), table);
        System.out.println(table);
    }
}
